////
////  BinaryTree.c
////  Tree
////
////  Created by Xavier on 2023/11/21.
////


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "Queue.h"

typedef char ElemType;

//定义二叉树
typedef struct BinaryTree {
    ElemType data;
    struct BinaryTree *left_child;
    struct BinaryTree *right_child;
}BTNode;

//创建结点
BTNode* CreateNode(ElemType element) {
    BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
    if (newNode == NULL) {
        printf("malloc is error!\n");
        exit(-1);
    }
    newNode->data = element;
    newNode->left_child = newNode->right_child = NULL;
    return newNode;
}

//创建二叉树
/**
            A
        B                C
           D    E      F
 
 */
BTNode* CreateTree(void) {
    BTNode* node1 = CreateNode('A');
    BTNode* node2 = CreateNode('B');
    BTNode* node3 = CreateNode('C');
    BTNode* node4 = CreateNode('D');
    BTNode* node5 = CreateNode('E');
    BTNode* node6 = CreateNode('F');
    
//    node1->left_child = node2;
//    node1->right_child = node3;
//    node2->right_child = node4;
//    node3->left_child = node5;
//    node3->right_child = node6;
    
    node1->left_child = node2;
    node1->right_child = node3;
    node2->left_child = node4;
    node2->right_child = node5;
    node3->left_child = node6;
    return node1;
}

//前序遍历 - ABDCEF
void PreOrder(BTNode* root){
    if (root == NULL) {
        printf("");
        return;
    }
    printf("%c ", root->data);
    PreOrder(root->left_child);
    PreOrder(root->right_child);
}
 
//中序遍历 - BDAECF
void InOrder(BTNode* root){
    if (root == NULL) {
        printf("");
        return;
    }
    InOrder(root->left_child);
    printf("%c ", root->data);
    InOrder(root->right_child);
}

//后序遍历 - DBEFCA
void PostOrder(BTNode* root){
    if (root == NULL) {
       //printf("");
        return;
    }
    PostOrder(root->left_child);
    PostOrder(root->right_child);
    printf("%c ", root->data);
}

//层序遍历 - ABCDEF
/**
 要借助队列的特性，先进先出，核心思想：上一层次带下一层次
 */
void SequenceOrder(BTNode* root){
    Queue q;
    QueueInit(&q);

    if (root)
    {
        QueuePush(&q, root);
    }

    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);

        printf("%c ", front->data);
        if (front->left_child)
        {
            QueuePush(&q, front->left_child);
        }

        if (front->right_child)
        {
            QueuePush(&q, front->right_child);
        }
    }

    printf("\n");
    //QueueDestory(&q);
    
}

//根据前序遍历创建二叉树
void CreateBTreeByPreOrder(BTNode* root);

//判断结点的个数
int BTNodeSize(BTNode* root) {
    if (root == NULL) return 0;
    else
    return BTNodeSize(root->left_child) + BTNodeSize(root->right_child) + 1;
}

//判断叶子结点的个数
int BTLeafNodeSize(BTNode* root) {
    if (root == NULL) return 0;
    if (root->left_child == NULL && root->right_child == NULL) return 1;
    return BTLeafNodeSize(root->left_child) + BTLeafNodeSize(root->right_child);
}

//判断第k层结点的个数 k>=1
int BTSizeOfTier(BTNode *root, int k) {
    assert(k>=1);
    if (root == NULL) return 0;
    if (k == 1) return 1;
    
    return BTSizeOfTier(root->left_child, k-1) + BTSizeOfTier(root->right_child, k-1);
}

//二叉树的深度
int BTDeapth(BTNode *root) {
    if (root == NULL) return 0;
    int m = BTDeapth(root->left_child);//左子树的总的深度
    int n = BTDeapth(root->right_child);//右子树的总的深度
    return m>n?m+1:n+1;
}

//二叉树查找值为x的结点
BTNode* FindBTree(BTNode *root, ElemType x) {
    if (root == NULL) return NULL;
    if (root->data == x) return root;
    return FindBTree(root->left_child, x);
    return FindBTree(root->right_child, x);
    
    return NULL;
}

//是否为满二叉树
bool FullBTree(BTNode *root) {
    return true;
}

//二叉树的销毁
void DestroyBTree(BTNode *root){
    if (root == NULL) return;
    
    DestroyBTree(root->left_child);
    DestroyBTree(root->right_child);
    free(root);
}
int main(void) {
    BTNode* tree = CreateTree();
    printf("前序遍历：");
    PreOrder(tree);
    printf("\n");
    
    printf("中序遍历：");
    InOrder(tree);
    printf("\n");
    
    printf("后序遍历：");
    PostOrder(tree);
    printf("\n");
    
    printf("层序遍历：");
    SequenceOrder(tree);
    printf("\n");
    
    printf("二叉树所有结点的个数：");
    printf("%d\n", BTNodeSize(tree));
    
    printf("二叉树所有叶子结点的个数：");
    printf("%d\n", BTLeafNodeSize(tree));
    
//    int num=0;
//    printf("请输入你想看二叉树第几层结点的个数：");
//    scanf("%d", &num);
    printf("二叉树第%d层结点的个数为：%d\n",2, BTSizeOfTier(tree, 2));
    
    printf("二叉树的深度为：%d\n", BTDeapth(tree));

    printf("查找二叉树值为：");
    BTNode* tmp = FindBTree(tree, 'A');
    printf("%c\n", tmp->data);

    
}




